The present invention relates to methods, a controller and a system for allocating access to time slots used for transferring data between nodes in a time multiplexed network, such as a Dynamic Synchronous Transfer Mode (DTM) network, whose bandwidth is divided into cycles which in turn are divided into control slots for control signalling and data slots for transferring data, wherein slots allocated to a primary home node may be temporarily allocated to a temporary home node, said temporary home node instead of said primary home node then temporarily having the write access to said slots, and subsequently reallocated to said primary home node.
As an example of a time multiplexed network, DTM is a broadband network architecture (see e.g., Christer Bohm, Per Lindgren, Lars Ramfelt, and Peter Sjxc3x6din, The DTM Gigabit Network, Journal of High Speed Networks, 3(2), pp 109-126, 1994 and Lars Gauffin, Lars H{dot over (a)}kansson, and Bjxc3x6rn Pehrson, Multi-gigabit networking based on DTM, Computer Networks and ISDN Systems, 24(2), pp 119-139, April 1992). DTM is a circuit switched network and intended to be used in public networks as well as in local area networks (LAN""s). It uses channels as the communication abstraction. The channels differ from telephony circuits in various ways. First, establishment delay is short so that resources can be allocated/reallocated dynamically as fast as user requirements change. Second, they are simplex and so minimise overhead when the communication is unidirectional. Third, they offer multiple bit-rates to support large variations in user capacity requirements. Finally, they are multicast, allowing several destinations.
DTM channels share many beneficial properties with circuits. There is no transfer of control information after channel establishment, resulting in very high utilisation of network resources for large data transfers. Support of real-time traffic is natural; there is no need for policing, congestion control or flow-control within the network. The control information is separated from data, which makes multicast less complex. The transmission delay is negligible (i.e., less than 125 ms) and there is no potential for data loss because of buffer overflow as in ATM (Asynchronous Transfer Mode). Bit-error rates depend on the underlying link technologies, and switches are simple and fast due to strict reservation of resources at channel set-up. DTM can show good performance in areas where traditional circuit-switched networks fall short: dynamic bandwidth allocation, channel establishment delay, and as shared media networks.
The basic topology of a DTM network is preferably a bus with two unidirectional optical fibers connecting all nodes, but can also be realised by any other kind of structure, e.g., a ring structure. The DTM medium access protocol is a time-division multiplexing scheme. The bandwidth of the bus is divided into 125 xcexcs cycles, which in turn are divided into 64-bit time slots. The number of slots in a cycle thus depends on the network""s bit-rate. The slots are divided into two groups, control slots and data slots. Control slots are generally static and used to carry messages for the network""s internal operation. The data slots are used to transfer user data between the nodes.
Generally, in each network node there is a node controller, which controls the access to data slots and performs network management operations.
Control slots are used exclusively for control messages between these node controllers. Each node controller preferably has write access to at least one control slot in each cycle, which it uses to multicast control messages to other node controllers. Here, multicast refers to sending information to one or more downstream nodes on a bus, as the transmission medium is unidirectional. Since write access to control slots is exclusive, the node controller always has access to its control slots regardless of other nodes and network load.
The majority of the slots in a cycle are data slots. Access to data slots changes over time, according to traffic demands. Write access to slots is controlled by slot access, sometimes referred to as slot tocens. A node controller may write data into a specific slot only if the node has write access to this specific slot. The slot access protocol, or token protocol, guarantees the slot access to be conflict free, which means that several nodes do not write data into the same slot.
One optimisation in slot access management is to introduce so called block access or block tokens, i.e. access to a number of slots arranged contiguously in a slot range. A block token, i.e. access to a group of slots, may be transferred in a single control message, but can only be used for particular combinations of slots. For instance, block access may be denoted by a slot number and an offset giving the number of contiguous slots in the group or block.
Also, write access to slots (single or block) may be exchanged or varied between different nodes during network operation, for example as a result of a node asking for more transferring capacity by requesting write access to more slots from other nodes. One of the major problems with this kind of write access allocation is fragmentation. The average number of contiguous available time slots allocated to a node of a DTM-like network is small due to the random movement and exchange of slot access and the varying capacity of users"" requests. This gives relatively long access delays (in the millisecond region) for high capacity channels, particularly at moderate to high load.
One way of dealing with this fragmentation problem is to define a home node for each slot at network start-up or during network operation. This is preferably done in such a way that slots having the same home node preferably define at least partly a continuous slot range. The nodes may then xe2x80x9cborrowxe2x80x9d available or free slots from each other, sending back free slots to their respective home node, for example when a significant time has passed. Also, two or more consecutive slots are preferably merged into a single block token when existing in the free pool of a node.
Hence, in a DTM-like system of this kind, a first node may have write access to a first set of slots and a second node may have write access to a second set of slots. Then, the first node is said to be the primary home node of the first set of slots and the second node is said to be the primary home node for the second set of slots. However, if the first node at some time require more transferring capacity to fulfil the demands of one or more users attached to the first node, it may temporarily lend or borrow slots from another node, for example the second node, presently having a surplus of slots. In such a case, one or more slots having the second node as primary home node may be temporarily allocated to the first node, the first node then being a so called temporary home node of said one or more borrowed slots and hence temporarily having the write access thereto. When the demand for transferring capacity in the first node decreases, or for example after a predefined time interval or, said one or more borrowed slots are returned to their primary or actual home node, i.e. the second node.
However, nodes in, e.g., an integrated services network will have different load depending on the equipment attached to it. Also, the load will vary in time. In case of non-uniform traffic, a node that requires high capacity may have to regularly borrow slots from and return slots to their respective home node, which results in overhead for slot negotiation and longer set-up times for the channels.
The object of the invention is to avoid the problems mentioned above with overhead for slot access negotiation in a time multiplexed network, such as a Dynamic Synchronous Transfer Mode (DTM) network, whose bandwidth is divided into cycles, which in turn are divided into time slots comprising control slots for control signalling and data slots for transferring data.
According to the invention, this and other objects are achieved by a method, a controller and a system having the features presented in the accompanying claims.
Hence, according to one aspect, the invention is preferably provided in a network wherein slots allocated to a primary home node may be temporarily allocated to a temporary home node, said temporary home node instead of said primary home node then temporarily having the write access to said slots, and subsequently reallocated to said primary home node.
According to the invention, the degree of temporary allocation of slots to a first node is evaluated and, based upon this evaluation, the number of slots having said first node as primary home node is increased in response thereto in order to decrease the need for temporary allocation of slots within said network.
Preferably, the transfer of slot ownership is initiated by a request from the node having a lack of slot capacity. Such a request, or any other type of reallocation initiation, may for example be provided when the node has borrowed slots a predifined number of times, when the ratio between the number of slots having the node as temporary home node and the number of slots having the node as primary home node exceeds a predefined value, when the allocation or xe2x80x9cloanxe2x80x9d has to be directed over a substantial distance over the network. As another alternative, a predefined fraction or a predefined number of slots may be arranged to change owner, i.e. primary home node, each time one node borrows slots from another as a result of the loan itself.
Hence, according to the invention slots may be reallocated to new home nodes during network operation. In one embodiment, a first node sends a request to a second node to get more slots assigned to it as primary home node and the second node transfers slots to the first node so that the slot capacity assigned to the first node as primary home node is increased and the slot capacity assigned to the second node as primary home node is decreased. Preferably, the allocation is done in such a way that the tokens that will share the same primary home node will define at least partly a continuous slot range.
Preferably, slots having the same primary home node define a continuous slot range. Then, all nodes assigned as primary home nodes for slots located, in a cycle, in-between slots having a first node as primary home node and slots having a second node as primary home node may transfer slot write access in the following way.
The second node is assigned as present node. Write access to a number of slots, amounting to the number requested by the first node, having the present node as primary home node and neighbouring a slot range having a next node as primary home node are reallocated from the present node to the next node, said slot range of the next node either being the slot range of the first node or being a slot range of a node located in between the slot ranges of the first and the second nodes. The distance between the slot range of the next node and the slot range of the first node is preferably smaller than the distance between the slot range of the present node and the slot range of the first node. In case of the next node not being the first node, the next node is assigned as the present node and the step of reallocating is repeated. This procedure is referred to as a xe2x80x9cpushxe2x80x9d, since write access to the requested number of slots is pushed from the second node to a next node to another next node and so on, until it has been pushed to the first node.
According to the invention, the problems mentioned above are avoided by efficiently reallocating slot access to new primary home nodes, so minimising overhead for slot access negotiation. The criteria for when a node should request more slots assigned to it as primary home node, which node it should ask and how much capacity it should request, can be chosen in various ways, as mentioned above and below. However, resilience has to be implemented in order to avoid oscillation and thus overhead for control signalling.
Preferably, but not necessarily, each node has a node controller, which controls the write access to slots and in which a home node is defined for each slot and free slots may be sent back to their respective home nodes when a significant time has passed.
An advantage of the invention is that it is a simple and easily implemented mechanism, which strongly improves the performance of the network. The probability of that a node has to temporarily borrow slots from another node is decreased.
A further advantage of the invention is that low fragmentation is maintained.
Yet another advantage is that the reallocation of a slot to a new home node may be realised even though the slot is in use, e.g., by another node temporarily having access to the node, i.e. being the temporary home node of said slot.
Still another advantage of the invention is that it, especially in combination with a slot reuse method, may further improve the bandwidth utilisation.